package list.p4_doublylist;

public class DoublyLinkedListWithoutHead implements list.p3_singlelist.IListWithoutHead{
    private static class Node {
        int val;
        Node next;
        Node prev;
        public Node(int val, Node prev, Node next) {
            this.val = val;
            this.next = next;
            this.prev = prev;
        }
    }

    private Node left;
    private Node right;
    @Override
    public void addFirst(int data) {
        left = new Node(data, null, left);
        if (right == null) right = left;
    }

    @Override
    public void addLast(int data) {
        if (left == null) {
            addFirst(data);
            right = left;
            return;
        }
        Node newNode = new Node(data, right, null);
        right.next = newNode;
        right = newNode;
    }

    @Override
    public boolean addIndex(int index, int data) {
        int size = size();
        if (index == size) addLast(data);
        if (index > size || index <0) return false;
        Node curr = left;
        while (index-- > 0) {
            curr = curr.next;
        }
        curr = new Node(data, curr.prev, curr);
        curr.prev.next = curr;
        curr.next.prev = curr;
        return true;
    }

    @Override
    public boolean contains(int key) {
        for (Node curr = left; curr != null; curr = curr.next) {
            if (curr.val == key) {
                return true;
            }
        }
        return false;
    }

    @Override
    public void remove(int key) {
        for (Node curr = left; curr != null; curr = curr.next) {
            if (curr.val == key) {
                curr.prev.next = curr.next;
                curr.next.prev = curr.prev;
                return;
            }
        }
    }

    @Override
    public void removeAllKey(int key) {
        for (Node curr = left; curr != null;) {
            if (curr.val == key) {
                if (curr == left) {
                    left = curr.next;
                    curr = left;
                    continue;
                }
                curr.prev.next = curr.next;
                curr.next.prev = curr.prev;
            } else {
                curr = curr.next;
            }
        }
    }

    @Override
    public int size() {
        int size = 0;
        Node cur = left;
        for (; cur != null; cur = cur.next, size++);
        return size;
    }

    @Override
    public void display() {
        System.out.print("[");
        for (Node curr = left; curr != null; curr = curr.next) {
            System.out.print(curr.next == null ? curr.val : curr.val + " <> ");
        }
        System.out.println("]");
    }

    @Override
    public void clear() {
        left = right = null;
    }
}
